import java.util.Arrays;
/**
 * @ClassName: Algorithm-and-Data-Structure
 * @Description:
 * @Author: zhouhong
 * @Create: 2021-04-07 21:59
 **/
public class MergeSortTest {
    private MergeSortTest(){}
    public static void sort(int[] arr){
        sort(arr, 0, arr.length - 1);
    }
    private static void sort(int[] arr, int l, int r){
        if (l >= r){
            return;
        }else {
            int mid = l + (r - l) / 2;
            sort(arr, l, mid);
            sort(arr, mid + 1, r);
            // 小优化：已经排序的两个数组，如果左边数组的最右边（最大数）小于右边数组的
            // 最左边（最小）说明不必要归并了
            if (arr[mid] > arr[mid + 1]){
                merge(arr, l, mid, r);
            }
        }
    }
    // 合并两个有序的区间，使得合并后的新数组也为有序 arr[l, mid] 和 arr[mid + 1, r]
    private static void merge(int[] arr, int l, int mid, int r){
        // 开辟一个新数组---一份拷贝，用于将它里面的值赋值给原数组
        int[] temp = Arrays.copyOf(arr, arr.length);
        // 两个指针，i 指向l、j指向中间位置
        int i = l, j = mid + 1;
        for (int k = l; k <= r; k++) {
            if (i > mid){
                arr[k] = temp[j];
                j ++;
            }else if (j > r){
                arr[k] = temp[i];
                i ++;
            }else if (temp[i] <= temp[j]){
                arr[k] = temp[i];
                i ++;
            }else {
                arr[k] = temp[j];
                j ++;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {1,23,3,43,5,2,65,76,2,34,56,2,7,88,875};
        sort(arr);
        for (int a : arr) {
            System.out.println(a);
        }
    }
}
